1. Field of the Invention
This invention relates to an efficient method for determining and selecting a next available unique identifier from a group of unique identifiers.
2. Description of Prior Art
Conventional methods are used to assign a unique integer number for various applications which require identification of a unique number. For example, new telephone numbers are assigned by identifying deleted, used or otherwise available telephone numbers, such as those which either have not been previously assigned or which have expired. It is also necessary, for example, to identify expired or unissued unique numbers for credit card applications.
Conventional methods have also been used to assign a unique numeric tag to each program as programs are stored in a database. Some conventional methods use a linear approach for determining an available program number from a range of unique program numbers available, from a minimum value to a maximum value, to a database.
A conventional linear approach includes a linear search that starts at a minimum allowable integer and the search function checks a number or value versus the used numbers or values in the database. If the minimum allowable number or value is not used in the database that number is defined as a unique identifier. Otherwise, the next ascending number is checked. This iteration continues until all possible numbers are checked. This conventional method requires constant queries of the database which is slow and inefficient.
There is an apparent need for a method which is more efficient than the conventional linear method for determining a next available program number or other identifier.
It is one object of this invention to provide an efficient method for finding a unique integer from a range of acceptable integers by dividing the range of acceptable integers into a number of equally sized banks and using a maximum value of the integer in each bank plus one as a unique integer value.
It is another object of this invention to provide a method that first employs a search for maximum values of identifiers within a bank, and then defaults to conventional method steps, such as the previously mentioned conventional method steps, if the maximum value approach unsuccessfully identifies an available identifier after a specified number of tries.
One particular use for the method of this invention is to assign a unique program number to each program that a third party may transmit by any suitable transmission system. Transmitted programs may contain information such as a program title, a program description, a channel on which the program can be accessed, and a start time or a stop time of a program. For example, the numeric value 5 can be used to identify a program xe2x80x98NEWSxe2x80x99 which has a program description xe2x80x98LOCAL 5 O""CLOCK NEWSxe2x80x99, such as on television channel 5. Such program information can be stored in a database and later downloaded to an end user facility. For example, program information identifying television, radio or computer transmissions can be downloaded to and displayed at the end user facility, which may be a television, a cable box, a computer, a telephone or the like.
Any suitable type of database which supports a form of structured query language (SQL) can be used to store programs. Each program in the database has a unique identifier assigned to the particular program, for future use. In one preferred embodiment of this invention, the unique identifiers will be a group of integer numbers. The size of the group can vary as a function of the data.
Because certain programs may expire or be deleted, previously assigned unique identifiers again become available, but not necessarily in a sequential order. Thus, it is necessary to search the group of unique identifiers to determine which, if any, unique identifiers are currently available to qualify as a next available identifier.
In an effort to minimize the number of times that a database must be queried, it is possible to divide an overall range of unique identifiers into a series of banks each having a plurality of unique identifiers. In one preferred embodiment according to this invention, each of the banks, when empty, has an available minimum value identifier and an available maximum value identifier. The total quantity of resident identifiers in each bank can be counted and used to find the bank of identifiers that is most empty.
Once the resident identifiers are counted, which may correspond to a quantity of programs in a database bank for example, a first available bank having a lowest counted number of resident identifiers is determined. Within the first available bank, a highest value of the resident identifiers is also determined, for example, by using a SQL xe2x80x98MAXxe2x80x99 query. Within the first available bank, the maximum value of the resident identifiers is compared to an available maximum value an identifier may have in a particular bank.
When the highest value is less than the maximum value, within the first available bank, the next available identifier can be assigned as a sum of the highest value plus a defined incremental value. However, if the highest value is greater than or equal to the maximum value, in the first available bank, the method of this invention then identifies a second available bank which has a lowest counted number equal to or less than the lowest counted number of the first available bank. In the second available bank, a highest value of the unique numbers is determined. The highest value is compared to a maximum value an identifier may take on in the second available bank.
If the highest value is less than the maximum value, in the second available bank, the next available identifier is assigned a value equal to a sum of the second highest value plus the incremental value. However, in one preferred embodiment of this invention, if the highest value in the second available bank is greater than or equal to the maximum value in the second available bank, then the method of this invention defaults to linearly searching the second available bank to determine the next available identifier.
The unique identifier found is stored as a last maximum identifier. When subsequent unique identifiers are requested, a bank of integers may not be determined and a new maximum does not necessarily need to be found using the SQL MAX query. The last maximum value stored plus one is a new unique identifier, as long as such value does not exceed the maximum value allowable in the database bank. New banks of integers are selected in at least two instances: (1) when a maximum value plus one in the database bank exceed; an upper limit of acceptable values in the database bank; and (2) at the start of the program, such as via initialization of a check bank counter to a size greater than the size of the database bank.